1. Field of the Invention
The present invention generally relates to cache memory in computer systems, and more particularly to cache replacement systems and methods for reducing latency in non-uniform cache architectures.
2. Description of the Related Art
On-chip cache memories are usually size-limited by area, power, and latency constraints. These cache memories are often not able to accommodate the whole working set of a given program. When a program references a piece of data that is not present in the cache, a cache miss occurs and a request is sent to a next level of the cache hierarchy for the missing data. When the requested data eventually arrives from the next level, a decision must be made as to which data currently in the cache should be evicted to make room for the new data.
These algorithms are called cache replacement algorithms. The most commonly employed cache replacement algorithms are random, first in first out (FIFO), and least recently used (LRU). Except for the random replacement algorithm, all replacement algorithms base their replacement decision on a ranking of all cache lines in the set where the new data will be stored. For example, the LRU replacement algorithm tracks the access ordering of cache lines within a cache set, while the FIFO replacement algorithm ranks the cache lines by their allocation order. The least recently accessed/allocated cache lines are given the highest ranking and upon cache miss, they are chosen to be replaced.
Prior work on replacement algorithms does not consider the access latency to each cache line, because in logic-dominated cache designs all cache lines have the same access latency. Recently, wire delay has played a more significant role in access latencies. Consequently, access latencies to different cache partitions have grown further apart. Therefore, there is a need for a new cache replacement algorithm that considers access latencies while formulating a replacement decision to reduce average latencies to lines stored in different partitions of a cache.